package com.fps.webshop.question.question0001_0099;

import java.util.Stack;

/**
 * 20. 有效的括号
 * 
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 
 * 有效字符串需满足：
 * 		左括号必须用相同类型的右括号闭合。
 * 		左括号必须以正确的顺序闭合。
 *  
 * 示例 1：
 * 输入：s = "()"
 * 输出：true
 * 
 * 示例 2：
 * 输入：s = "()[]{}"
 * 输出：true
 * 
 * 示例 3：
 * 输入：s = "(]"
 * 输出：false
 * 
 * 示例 4：
 * 输入：s = "([)]"
 * 输出：false
 * 
 * 示例 5：
 * 输入：s = "{[]}"
 * 输出：true
 * 
 * 提示：
 * 		1 <= s.length <= 10^4
 * 		s 仅由括号 '()[]{}' 组成
 */
public class Question020 {

	/**
	 * 第一次提交，栈的简单应用
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		1 ms	36.4 MB	Java	2021/08/18 10:31
	 * 
	 * 执行用时：1 ms, 在所有 Java 提交中击败了99.25%的用户
	 * 内存消耗：36.4 MB, 在所有 Java 提交中击败了68.60%的用户
	 */
	public static boolean isValid(String s) {
		Stack<Character> tric = new Stack<Character>();
		for(char ss:s.toCharArray()) {
			if(ss=='('||ss=='['||ss=='{') {
				tric.push(ss);
			}else {
				if(ss==')'&&(tric.empty()||tric.pop()!='(')) {
					return false;
				}else if(ss==']'&&(tric.empty()||tric.pop()!='[')) {
					return false;
				}else if(ss=='}'&&(tric.empty()||tric.pop()!='{')) {
					return false;
				}
			}
		}
		if(tric.empty()) {
			return true;
		}else {
			return false;
		}
    }
	
	/**
	 * 第二次提交，试着玩，鬼才代码wwwww
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		48 ms	39 MB	Java	2021/08/18 10:35
	 * 
	 * 执行用时：48 ms, 在所有 Java 提交中击败了5.00%的用户
	 * 内存消耗：39 MB, 在所有 Java 提交中击败了5.03%的用户
	 */
	public boolean isValid2(String s) {
        while(s.contains("()")||s.contains("[]")||s.contains("{}")){
            if(s.contains("()")){
                s=s.replace("()","");
            }
            if(s.contains("{}")){
                s=s.replace("{}","");
            }
            if(s.contains("[]")){
                s=s.replace("[]","");
            }
        }
        return s.length()==0;
    }
	
	public static void main(String[] args) {
		System.out.print(isValid("(]"));
	}
}
